package offer.offer02;

import java.util.Deque;
import java.util.LinkedList;
import java.util.Stack;

/**
 * 用一个dequeue来实现栈的功能, 使用两个指针来确定pushed和popped中扫描的3位置,
 * 在push进与popped第一个值相同的值时, 扫描看看能不能将dequeue中更多的值pop出去;
 * if(popLoc == popLen) return true;这种傻傻的, 在每一个地方都要添加的判断是否到达边界的语句不要加;
 *
 * 就创建一个栈模拟一下压入弹出, 遇到一样的就弹出看看最后栈是否为空。
 */
public class Solution31 {
    public boolean validateStackSequences(int[] pushed, int[] popped) {
        Deque<Integer> pushStack = new LinkedList<>();
        int pushLen = pushed.length;
        int popLen = popped.length;
        if(pushLen != popLen) return false;
        if(pushLen == 0) return true;
        int popLoc = 0;
        for(int i = 0; i < pushLen; i ++){
            if(pushed[i] != popped[popLoc]){
                pushStack.add(pushed[i]);
            }else{
                pushStack.add(pushed[i]);
//                popLoc ++ ;
//                if(popLoc == popLen) return true;
                while(pushStack.size() != 0 && popped[popLoc] == pushStack.getLast()){
//                    if(popLoc == popLen - 1) return true;
                    popLoc ++ ;
                    pushStack.removeLast();
                }
            }
        }

        return pushStack.size() == 0;
    }

    // 想想如果可以有重复值, 应该怎么做。
    public boolean validateStackSequences2(int[] pushed, int[] popped) {
        Stack<Integer> stack = new Stack<>();
        int i = 0;
        for(int num : pushed) {
            stack.push(num); // num 入栈
            while(!stack.isEmpty() && stack.peek() == popped[i]) { // 循环判断与出栈
                stack.pop();
                i++;
            }
        }
        return stack.isEmpty();
    }


    public static void main(String[] args) {
        int[] a = new int[] {1, 0};
        int[] b = new int[] {1, 0};
        System.out.println(new Solution31().validateStackSequences(a, b));
    }
}
